package com.me.study.arithmeticAndDataStructure.sort;

import com.me.common.util.PrintUtil;

/**
 * 堆排序
 *
 * @author ME
 * @date 2019/2/23 16:26
 */
public class HeapSort {

    public static void main(String[] args) {
        // Integer[] arr = new Integer[] { 10, 5, 13, 7, 19, 6, 20, 13, 3 };
        // PrintUtil.printArray(arr);
        // buildMaxHeap1(arr.length, arr);
        // PrintUtil.printArray(arr);

        HeapSort heap = new HeapSort();
        System.out.println("\n==================");
        Integer[] arr2 = new Integer[] { 10, 5, 13, 7, 19, 6, 20, 13, 3 };
        PrintUtil.printArray(arr2);
        heap.buildMaxHeap2(arr2);
        System.out.println("建立初始堆：");
        PrintUtil.printArray(arr2);

        heap.heapSort(arr2);
        System.out.println("排序后：");
        PrintUtil.printArray(arr2);

    }

    /**
     * 堆排序
     * @param list
     */
    public void heapSort(Integer[] list) {
        for (int i = list.length - 1; i > 0; i--) {
            // 最后一个元素和第一元素进行交换
            int temp = list[i];
            list[i] = list[0];
            list[0] = temp;

            // 筛选 R[0] 结点，得到i-1个结点的堆
            maxHeapAdjust(list, 0, i);
            System.out.format("第 %d 趟: \t", list.length - i);
            printPart(list, 0, list.length - 1);
        }
    }

    /**
     * 构建大顶堆2，
     * TODO 推荐: 从后往前调整，1次调整成功，性能更好
     */
    private void buildMaxHeap2(Integer[] array) {
        for (int i = array.length / 2; i >= 0; i--) {
            maxHeapAdjust(array, i, array.length);
        }
    }

    /**
     * 调整为大顶堆
     * @param array
     * @param parent
     * @param length
     */
    public void maxHeapAdjust(Integer[] array, int parent, int length) {
        int temp = array[parent]; // temp保存当前父节点
        int child = 2 * parent + 1; // 先获得左孩子

        while (child < length) {
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }

            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp >= array[child])
                break;

            // 把孩子结点的值赋给父结点
            array[parent] = array[child];

            // 选取孩子结点的左孩子结点,继续向下筛选
            parent = child;
            child = 2 * child + 1;
        }

        array[parent] = temp;
    }

    // 打印序列
    public static void printPart(Integer[] list, int begin, int end) {
        for (int i = 0; i < begin; i++) {
            System.out.print("\t");
        }
        for (int i = begin; i <= end; i++) {
            System.out.print(list[i] + "\t");
        }
        System.out.println();
    }

    /**
     * 构建大顶堆1
     */
    private static void buildMaxHeap1(int n, Integer[] data) {
        for (int i = 1; i < n; i++) {
            int t = i;
            // 调整堆
            while (t != 0 && data[parent(t)] < data[t]) {
                int temp = data[t];
                data[t] = data[parent(t)];
                data[parent(t)] = temp;
                t = parent(t);
            }
        }
    }

    /**父节点*/
    private static int parent(int n) {
        return (n - 1) / 2;
    }

    /**左孩子*/
    private static int left(int n) {
        return 2 * n + 1;
    }

    /**右孩子*/
    private static int right(int n) {
        return 2 * n + 2;
    }

}
